package com.gxc.integer;

/**
 * 51. N 皇后
 * 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
 *
 * n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 *
 * 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
 *
 * 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 */
import java.util.*;

public class SolveNQueens {

    public static void main(String[] args) {
        print(handle(5));
    }

    public static List<List<String>> handle(int n) {
        List<List<String>> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int[] cur = new int[n];
            int[] left = new int[n];
            int[] right = new int[n];
            List<Integer> list = new ArrayList<>();
            cur[i]=1;
            left[i]=1;
            right[i]=1;
            list.add(i);
            recursion(cur, left, right, 1, list, res);
        }
        return res;
    }

    /**
     * 1.递归按层选皇后
     * 2.上一层皇后的位置影响下一层皇后位置当前位置和左右两个位置
     * @param cur 当前所有层选中的皇后位置
     * @param left 当前所有层选中的皇后位置左斜线的位置
     * @param right 当前所有层选中的皇后位置右斜线的位置
     * @param row  当前层数
     * @param list 记录当前层选择的皇后位置
     */
    private static void recursion(int[] cur, int[] left, int[] right, int row, List<Integer> list, List<List<String>> res) {
        if (row == cur.length) {
            List<String> str = new ArrayList<>();
            for (int j = 0; j < cur.length; j++) {
                Integer index = list.get(j);
                StringBuilder sb = new StringBuilder();
                for (int m = 0; m < cur.length; m++) {
                    if (m == index) {
                        sb.append("Q");
                    } else {
                        sb.append(".");
                    }
                }
                str.add(sb.toString());
            }
            res.add(str);
            return;
        }
        //上一行所有选中的皇后左移
        for (int i = 1; i < left.length; i++) {
            left[i-1] = left[i];
        }
        left[left.length-1] = 0;
        //上一行所有选中的皇后右移
        for (int i = right.length-2; i >= 0; i--) {
            right[i+1] = right[i];
        }
        right[0] = 0;
        int[] curC = new int[cur.length];
        for (int i = 0; i < curC.length; i++) {
            curC[i] = cur[i];
        }
        int[] leftC = new int[cur.length];
        for (int i = 0; i < leftC.length; i++) {
            leftC[i] = left[i];
        }
        int[] rightC = new int[cur.length];
        for (int i = 0; i < rightC.length; i++) {
            rightC[i] = right[i];
        }
        for (int i = 0; i < cur.length; i++) {
            if (curC[i] == 0 && leftC[i] == 0 && rightC[i]==0) {
                //记录当前层选择的皇后位置
                list.add(i);
                curC[i]=1;
                leftC[i]=1;
                rightC[i]=1;
                recursion(curC, leftC, rightC, row+1, list, res);
                //回滚，继续尝试别的位置
                list.remove(row);
                /*curC = cur;
                leftC = left;
                rightC = right;*/
                for (int j = 0; j < curC.length; j++) {
                    curC[j] = cur[j];
                }
                for (int j = 0; j < leftC.length; j++) {
                    leftC[j] = left[j];
                }
                for (int j = 0; j < rightC.length; j++) {
                    rightC[j] = right[j];
                }
            }
        }
    }

    private static void print(List<List<String>> list) {
        for (List<String> strings : list) {
            for (String string : strings) {
                System.out.print(string + " ");
            }
            System.out.println("");
        }
    }

    class Solution {
        public List<List<String>> solveNQueens(int n) {
            List<List<String>> solutions = new ArrayList<List<String>>();
            int[] queens = new int[n];
            Arrays.fill(queens, -1);
            Set<Integer> columns = new HashSet<Integer>();
            Set<Integer> diagonals1 = new HashSet<Integer>();
            Set<Integer> diagonals2 = new HashSet<Integer>();
            backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2);
            return solutions;
        }

        public void backtrack(List<List<String>> solutions, int[] queens, int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) {
            if (row == n) {
                List<String> board = generateBoard(queens, n);
                solutions.add(board);
            } else {
                for (int i = 0; i < n; i++) {
                    if (columns.contains(i)) {
                        continue;
                    }
                    //
                    int diagonal1 = row - i;
                    if (diagonals1.contains(diagonal1)) {
                        continue;
                    }
                    //层数 +i  表示便宜量
                    int diagonal2 = row + i;
                    if (diagonals2.contains(diagonal2)) {
                        continue;
                    }
                    //当前行皇后的col坐标
                    queens[row] = i;
                    columns.add(i);
                    diagonals1.add(diagonal1);
                    diagonals2.add(diagonal2);
                    backtrack(solutions, queens, n, row + 1, columns, diagonals1, diagonals2);
                    queens[row] = -1;
                    columns.remove(i);
                    diagonals1.remove(diagonal1);
                    diagonals2.remove(diagonal2);
                }
            }
        }

        public List<String> generateBoard(int[] queens, int n) {
            List<String> board = new ArrayList<String>();
            for (int i = 0; i < n; i++) {
                char[] row = new char[n];
                Arrays.fill(row, '.');
                row[queens[i]] = 'Q';
                board.add(new String(row));
            }
            return board;
        }
    }

    class Solution2 {
        public List<List<String>> solveNQueens(int n) {
            int[] queens = new int[n];
            Arrays.fill(queens, -1);
            List<List<String>> solutions = new ArrayList<List<String>>();
            solve(solutions, queens, n, 0, 0, 0, 0);
            return solutions;
        }

        /**
         * 位运算
         * @param solutions
         * @param queens
         * @param n
         * @param row
         * @param columns
         * @param diagonals1
         * @param diagonals2
         */
        public void solve(List<List<String>> solutions, int[] queens, int n, int row, int columns, int diagonals1, int diagonals2) {
            if (row == n) {
                List<String> board = generateBoard(queens, n);
                solutions.add(board);
            } else {
                //(1 << n) - 1  获取全是1111... 的二进制数字
                int availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2));
                while (availablePositions != 0) {
                    //x & (−x) 可以获得 x 的二进制表示中的最低位的 1 的位置；
                    int position = availablePositions & (-availablePositions);
                    //x & (x−1) 可以将 x 的二进制表示中的最低位的 1 置成 0。
                    availablePositions = availablePositions & (availablePositions - 1);
                    //计算最低位1的index
                    int column = Integer.bitCount(position - 1);
                    queens[row] = column;
                    solve(solutions, queens, n, row + 1, columns | position, (diagonals1 | position) << 1, (diagonals2 | position) >> 1);
                    queens[row] = -1;
                }
            }
        }

        public List<String> generateBoard(int[] queens, int n) {
            List<String> board = new ArrayList<String>();
            for (int i = 0; i < n; i++) {
                char[] row = new char[n];
                Arrays.fill(row, '.');
                row[queens[i]] = 'Q';
                board.add(new String(row));
            }
            return board;
        }
    }

}
